Skip to main content

Single Number II

LeetCode 137 | Difficulty: Medium​

Medium

Problem Description​

Given an integer array nums where every element appears three times except for one, which appears exactly once. Find the single element and return it.

You must implement a solution with a linear runtime complexity and use only constant extra space.

Example 1:

Input: nums = [2,2,3,2]
Output: 3

Example 2:

Input: nums = [0,1,0,1,0,1,99]
Output: 99

Constraints:

- `1 <= nums.length <= 3 * 10^4`

- `-2^31 <= nums[i] <= 2^31 - 1`

- Each element in `nums` appears exactly **three times** except for one element which appears **once**.

Topics: Array, Bit Manipulation

Approach​

Bit Manipulation​

Operate directly on binary representations. Key operations: AND (&), OR (|), XOR (^), NOT (~), shifts (<<, >>). XOR is especially useful: a ^ a = 0, a ^ 0 = a.

When to use

Finding unique elements, power of 2 checks, subset generation, toggling flags.

Solutions​

Solution 1: C# (Best: 104 ms)​

MetricValue
Runtime104 ms
Memory25.1 MB
Date2020-01-18
Solution
public class Solution {
    public int SingleNumber(int[] nums) {
        int ones = 0, twos = 0;
    for(int i = 0; i < nums.Length; i++){
        ones = (ones ^ nums[i]) & ~twos;
        twos = (twos ^ nums[i]) & ~ones;
    }
    return ones;
    }
}

Complexity Analysis​

ApproachTimeSpace
Bit Manipulation$O(n) or O(1)$$O(1)$

Interview Tips​

Key Points
  • Discuss the brute force approach first, then optimize. Explain your thought process.